#include <sys/syscall.h>
#include <mips/regdef.h>

	.text
	.align 	2
	.global mergesort
	.ent 	mergesort

mergesort:
	.frame	$fp, 56, ra

	.set noreorder
	.cpload	t9
	.set reorder

	subu	sp,sp,56

	# Guardo los registros
	.cprestore 40
	sw		ra,48(sp)
	sw		$fp,44(sp)
	move	$fp,sp

	# Guardo los parametros
	sw		a0, 56($fp) // cadena a ordenar
	sw		a1, 60($fp) // buffer resultado

	# llamo a la funcion length:
	lw		a0, 56($fp)
	jal		length
	sw      v0, 16($fp)	// length input
	
	# Si la cadena de entrada tiene longitud igual o menor
	# a uno, entonces termina.
	lw		t0, 16($fp)
	li		t1, 1
	ble 	t0, t1, devolver_el_primero
	
	# sino
	# obtengo la parte izquierda
	li		t1, 2
	div		t2, t0, t1
	sw		t2, 20($fp) // length buffer left
	
	# malloc de left
	lw		a0,	20($fp)
	addiu	a0, a0, 2
	jal 	mymalloc
	sw      v0, 24($fp) // buffer left
	
	# malloc de right
	lw		a0,	20($fp)
	addiu	a0, a0, 2
	jal 	mymalloc
	sw      v0, 32($fp) // buffer right
	
	# copio los primeros n chars del string de input a left
	li		t1, 0		// i
	lw		t2, 24($fp) // ptr a buffer left
	lw		t0, 56($fp) // ptr a originStr
	lw		t3,	20($fp) // length buffer left

loop_copia_left:
	beq		t1, t3, copiar_right
	lb		t4,	0(t0)
	sb		t4, 0(t2)
	addiu	t1, t1, 1 // i++
	addiu	t0, t0, 1
	addiu	t2, t2, 1

	sb		zero, 0(t2)	// fin de linea

	j 	loop_copia_left

copiar_right:
	# copio los ultimos n chars del string de input a right
	lw		t1, 20($fp)	// i = length buffer left
	lw		t2, 32($fp) // ptr a buffer right
	lw		t0, 56($fp) // ptr a originStr
	lw		t3,	16($fp) // length del original
	add 	t0, t0, t1	
loop_copia_right:
	beq	t1, t3, invocacion_recursiva
	lb	t4,	0(t0)
	sb	t4, 0(t2)
	addiu	t1, t1, 1 // i++
	addiu	t0, t0, 1
	addiu	t2, t2, 1	

	sb		zero, 0(t2)
	j 	loop_copia_right

invocacion_recursiva:
	# malloc del buffer resultado Left
	lw		a0,	20($fp)
	jal 	mymalloc
	sw      v0, 28($fp) // buffer resultado left
	
	# malloc del buffer resultado right
	lw		a0,	20($fp)
	jal 	mymalloc
	sw      v0, 36($fp) // buffer resultado right
	
	# vuelvo a llamar a mergesort con left
	lw	a0, 24($fp)
	lw	a1, 28($fp)
	jal	mergesort
	
	# vuelvo a llamar a mergesort con right
	lw	a0, 32($fp)
	lw	a1, 36($fp)
	jal	mergesort
	
	# hago un merge de los dos buffer ordenados
	# llamo a merge.
	lw	a0, 28($fp)	// izquierdo
	lw	a1, 36($fp) // derecho
	lw	a2,	60($fp)	// resultado
	jal	merge
	
	# free del buffer left
	lw		a0,	24($fp)
	jal 	myfree
	
	# free del buffer right
	lw		a0,	32($fp)
	jal 	myfree
	
	# free del buffer resultado left
	lw		a0,	28($fp)
	jal 	myfree

	# free del buffer resutlado right
	lw		a0,	36($fp)
	jal 	myfree	

	j	terminar_merge_sort

devolver_el_primero:
	lw	t0, 56($fp)
	lb	t1, 0(t0)
	lw	t2,	60($fp)
	sb	t1,	0(t2)
	
	addiu	t2, t2, 1
	sb	zero, 0(t2)
	
	j	terminar_merge_sort
	
terminar_merge_sort:

	# destruyo el stack
	move	sp, $fp
	lw	$fp, 44(sp)
	lw	ra,  48(sp)
	addu	sp, sp, 56

	j	ra
	.end	mergesort
	
	.rdata
str_esmenorauno: .asciiz	"Es menor a uno.\n"
str_prueba: .asciiz	"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\n"
str_salto: .asciiz	"\n"
str_finlinea: .asciiz	"\0"
